package cn.xiaolang.function.data_structure;

import java.util.Arrays;

/**
 * 518. 零钱兑换 II
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
 * 假设每一种面额的硬币有无限个。
 * 题目数据保证结果符合 32 位带符号整数。
 * <p>
 * 示例 1：
 * 输入：amount = 5, coins = [1, 2, 5]
 * 输出：4
 * 解释：有四种方式可以凑成总金额：
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * <p>
 * 示例 2：
 * 输入：amount = 3, coins = [2]
 * 输出：0
 * 解释：只用面额 2 的硬币不能凑成总金额 3 。
 * 示例 3：
 * <p>
 * 输入：amount = 10, coins = [10]
 * 输出：1
 * { @see https://leetcode.cn/problems/coin-change-2/ }
 */
public class No19coinChange2 {

    public static void main(String[] args) {
        No19coinChange2 algorithm = new No19coinChange2();
        System.out.println(algorithm.change(5, new int[]{1, 2, 5}));

    }

    /**
     *
     * 用 dp[x] 表示金额之和等于x的硬币组合数，目标是求dp[amount]。
     *
     * 由此可以得到动态规划的做法：
     *
     * 1. 初始化dp[0]=1；// 只有当不选取任何硬币时，金额之和才为0，因此只有1种硬币组合
     * 2. 遍历coins，对于其中的每个元素coin，进行如下操作：遍历i从coin到amount，将 dp[i−coin] 的值加到 dp[i]。
     * 3. 最终得到dp[amount] 的值即为答案。
     * 如果存在一种硬币组合的金额之和等于i−coin，则在该硬币组合中增加一个面额为coin的硬币，即可得到一种金额之和等于i的硬币组合
     *
     *
     * 复杂度分析
     *
     * 时间复杂度：O(amount×n)，其中amount是总金额，n是数组coins的长度。需要使用数组coins中的每个元素遍历并更新数组dp中的每个元素的值。
     * 空间复杂度：O(amount)，其中amount是总金额。需要创建长度为 amount+1 的数组 dp。
     *
     * 执行用时：2 ms, 在所有 Java 提交中击败了99.96%的用户
     * 内存消耗：39.4 MB, 在所有 Java 提交中击败了28.31%的用户
     */
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = dp[i] + dp[i - coin];
            }
        }
        return dp[amount];
    }
}
